Một số tự nhiên (1, 2, 3, 4, 5, 6, ...) được gọi là số nguyên tố nếu nó lớn hơn 1 và không thể được biểu diễn thành tích của hai số tự nhiên nhỏ hơn. Các số lớn hơn 1 không phải là số nguyên tố được gọi là hợp số.[2] Nói cách khác, n {\displaystyle n} là số nguyên tố nếu n {\displaystyle n} vật không thể chia đều thành nhiều nhóm nhỏ gồm nhiều hơn một vật,[3] hoặc n {\displaystyle n} dấu chấm không thể được sắp xếp thành một hình chữ nhật có chiều dài và chiều rộng nhiều hơn một dấu chấm.[4] Chẳng hạn, trong các số từ 1 đến 6, số 2, 3 và 5 là số nguyên tố vì không có số nào khác có thể chia hết được chúng (số dư bằng 0).[5] 1 không phải là số nguyên tố vì nó đã được loại trừ ra khỏi định nghĩa. 4 = 2 × 2 và 6 = 2 × 3 đều là hợp số.

Ước số của một số tự nhiên n {\displaystyle n} là các số tự nhiên có thể chia hết được n {\displaystyle n} . Mọi số tự nhiên đều có ít nhất hai ước số là 1 và chính nó. Nếu nó còn có thêm một ước số khác thì nó không thể là số nguyên tố. Từ ý tưởng đó mà ta có một định nghĩa khác về số nguyên tố: đó là những số chỉ có đúng hai ước số dương là 1 và chính nó.[6] Ngoài ra, còn có một cách diễn đạt khác nữa: n {\displaystyle n} là số nguyên tố nếu nó lớn hơn 1 và không có số nào trong các số 2 , 3 , … , n − 1 {\displaystyle 2,3,\dots ,n-1} có thể chia hết được nó.[7]

25 số nguyên tố đầu tiên (tất cả các số nguyên tố nhỏ hơn 100) là:[8]

Không có số chẵn n {\displaystyle n} lớn hơn 2 nào là số nguyên tố vì một số chẵn bất kỳ có thể được biểu diễn thành 2 × n / 2 {\displaystyle 2\times n/2} . Do đó, tất cả số nguyên tố ngoài số 2 là số lẻ và được gọi là số nguyên tố lẻ.[9] Tuơng tự, khi được viết trong hệ thập phân, tất cả số nguyên tố lớn hơn 5 đều có tận cùng là 1, 3, 7 hoặc 9. Các số có tận cùng là chữ số khác đều là hợp số: số có tận cùng là 0, 2, 4, 6 hoặc 8 là số chẵn, và số có tận cùng là 0 hoặc 5 thì chia hết cho 5.[10]

Tập hợp các số nguyên tố được ký hiệu là P {\displaystyle \mathbf {P} } [11] hoặc P {\displaystyle \mathbb {P} } .[12]